package dovs.peephole;

import java.io.PrintStream;
import java.lang.reflect.Constructor;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Formatter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import dovs.instructions.Ilabel;
import dovs.instructions.Instruction;
import dovs.instructions.Label;
import dovs.peephole.node.APatternCollection;
import dovs.peephole.node.APatternDecl;
import dovs.peephole.node.PExp;
import dovs.peephole.node.PInst;
import dovs.peephole.node.PPatternCollection;
import dovs.peephole.node.PPatternDecl;
import dovs.phases.Limits;

public class PeepholeDriver {
	public static PPatternDecl current_pattern;

	private List<APatternDecl> patterns;

	private static int sum_before = 0;

	private static int sum_after = 0;

	private InstructionList instructionlist;

	Map<Label, Integer> label_degree;

	Map<Label, InstructionList> label_target;

	Set<Label> removed_labels = new HashSet<Label>();

	Set<Label> dying_labels = new HashSet<Label>();

	Set<Label> referred_labels = new HashSet<Label>();

	private static class ClickComparator implements Comparator<PPatternDecl> {
		public int compare(PPatternDecl p1, PPatternDecl p2) {
			return p2.click_count - p1.click_count;
		}
	}

	public static void printStatistics(PPatternCollection patterncoll,
			PrintStream out) {
		PPatternDecl[] patterns = patterncoll.getPatterns().toArray(
				new PPatternDecl[0]);
		int max_name_length = 0;
		for (PPatternDecl pattern : patterns) {
			if (pattern.getName().getText().length() > max_name_length) {
				max_name_length = pattern.getName().getText().length();
			}
		}
		Arrays.sort(patterns, new ClickComparator());
		Formatter f = new Formatter(out);
		for (PPatternDecl pattern : patterns) {
			f.format(
					"%5d %s%"
							+ (max_name_length
									- pattern.getName().getText().length() + 1)
							+ "s%5d\n", pattern.click_count,
					pattern.getName().getText(), "", pattern.click_count
							* pattern.getSize().value);
		}
		f.format(
				"\nReduced total size from %d to %d (%d) instructions with stack size %d.\n",
				sum_before, sum_after, dovs.phases.CodeEmission.instructions, Limits.sum_stack);
	}

	public PeepholeDriver(APatternCollection patterncoll) {
		this.patterns = patterncoll.getPatterns();
	}

	public void optimize(List<Instruction> instructions) {
		// Build instruction list
		label_degree = new HashMap<Label, Integer>();
		label_target = new HashMap<Label, InstructionList>();
		instructionlist = new InstructionList(null, null, null);
		InstructionList ilp = instructionlist;
		for (Instruction inst : instructions) {
			ilp = add(ilp, inst);
			if (!(inst instanceof Ilabel)) {
				sum_before++;
			}
		}
		checkLabels();
		mergeLabels();
		checkLabels();

		boolean body_clicked, pos_clicked;
		do {
			body_clicked = false;

			InstructionList ilp_prev = instructionlist;
			while (ilp_prev != null && ilp_prev.next != null) {
				do {
					pos_clicked = false;

					for (PPatternDecl pattern : patterns) {
						pos_clicked |= click(pattern, ilp_prev);
						// We might point to a label that died
						while (ilp_prev.inst != null
								&& ilp_prev.inst instanceof Ilabel
								&& !label_target.containsKey(((Ilabel) ilp_prev.inst).getLabel())) {
							ilp_prev = ilp_prev.previous;
						}
					}

					body_clicked |= pos_clicked;
				} while (pos_clicked);

				ilp_prev = ilp_prev.next;
			}
		} while (body_clicked);

		instructions.clear();
		for (ilp = instructionlist.next; ilp != null; ilp = ilp.next) {
			instructions.add(ilp.inst);
			if (!(ilp.inst instanceof Ilabel)) {
				sum_after++;
			}
		}
	}

	InstructionList remove(InstructionList ilp) {
		InstructionList next = ilp.next;
		Instruction i = ilp.remove();
		// System.err.println("Removed "+i.toAsm());
		if (i.canJump()) {
			Label l = i.getTarget();
			label_degree.put(l, label_degree.get(l) - 1);
			if (label_degree.get(l) == 0) {
				dying_labels.add(l);
			}
		}
		if (i instanceof Ilabel) {
			Label l = ((Ilabel) i).getLabel();
			// System.out.println("Removing "+l.getName());
			removed_labels.add(l);
			label_target.remove(l);
		}
		return next;
	}

	InstructionList add(InstructionList ilp, Instruction i) {
		InstructionList new_ilp = ilp.insertAfter(i);
		if (i.canJump()) {
			Label l = i.getTarget();
			if (label_degree.containsKey(l)) {
				label_degree.put(l, label_degree.get(l) + 1);
			} else {
				label_degree.put(l, 1);
				referred_labels.add(l);
			}
		}
		if (i instanceof Ilabel) {
			Label l = ((Ilabel) i).getLabel();
			if (label_target.containsKey(l)) {
				throw new PeepholeException("Duplicate label " + l.getName());
			}
			if (!label_degree.containsKey(l)) {
				label_degree.put(l, 0);
				dying_labels.add(l);
			}
			label_target.put(l, new_ilp);
		}
		return new_ilp;
	}

	InstructionList removeLabel(Label l) {
		label_degree.remove(l);
		return remove(label_target.get(l));
	}

	@SuppressWarnings("unchecked")
	private void mergeLabels() {
		Map<Label, Label> label_replace = new HashMap<Label, Label>();
		InstructionList il;
		for (il = instructionlist; il.next != null; il = il.next) {
			while (il.inst instanceof Ilabel && il.next != null
					&& il.next.inst instanceof Ilabel) {
				label_replace.put(((Ilabel) il.next.inst).getLabel(),
						((Ilabel) il.inst).getLabel());
				// System.out.println(((Ilabel)il.next.inst).getLabel().getName()+"
				// -> "+((Ilabel)il.inst).getLabel().getName());
				remove(il.next);
			}
		}

		for (il = instructionlist; il.next != null; il = il.next) {
			if (il.next.inst.canJump()
					&& label_replace.containsKey(il.next.inst.getTarget())) {
				/* Replace instruction */
				Instruction i = il.next.inst;
				Class<? extends Instruction> icl = i.getClass();
				Constructor<? extends Instruction> con = (Constructor<? extends Instruction>)icl.getConstructors()[0];
				int nargs = con.getParameterTypes().length;
				Object[] args = new Object[nargs];
				for (int a = 0; a < nargs; a++) {
					args[a] = i.getArg(a);
					if (args[a] == i.getTarget()) {
						// System.out.println("Replacing "+icl.getName()+"
						// "+((Label)args[a]).getName()+" ->
						// "+label_replace.get((Label)args[a]).getName());
						args[a] = label_replace.get(args[a]);
					}
				}
				Instruction new_i;
				try {
					new_i = con.newInstance(args);
					// System.out.println(new_i.getTarget().getName());
				} catch (Exception e) {
					throw new RuntimeException(
							"Error in instruction instantiation", e);
				}
				remove(il.next);
				add(il, new_i);
			}
		}
	}

	private void checkLabels() {
		for (Label l : dying_labels) {
			if (label_target.containsKey(l) && label_degree.get(l) == 0) {
				// System.err.println("Label "+l.getName()+" died");
				removeLabel(l);
			}
		}

		for (Label l : removed_labels) {
			if (!label_target.containsKey(l) && label_degree.containsKey(l)
					&& label_degree.get(l) > 0) {
				throw new PeepholeException("Removed live label " + l.getName());
			}
		}

		for (Label l : referred_labels) {
			if (!label_target.containsKey(l)) {
				throw new PeepholeException("Referred dead label "
						+ l.getName());
			}
		}

		dying_labels.clear();
		removed_labels.clear();
		referred_labels.clear();
	}

	private boolean click(PPatternDecl pattern, InstructionList ilp_prev) {
		// System.err.print(".");
		current_pattern = pattern;
		Evaluate.init(pattern, ilp_prev, this);
		if ((Boolean) pattern.getMatch().eval()) {
			pattern.click_count++;
			// System.err.println("Pattern "+pattern.getName().getText()+"
			// clicked");
			InstructionList ilp = ilp_prev.next;
			while (ilp.inst instanceof Ilabel) {
				ilp = ilp.next;
			}
			for (int n = 0; n < pattern.getSize().value; n++) {
				while (ilp.inst instanceof Ilabel) {
					ilp = remove(ilp);
				}
				if (ilp == null) {
					throw new PeepholeException("Pattern "
							+ pattern.getName().getText()
							+ " tried to remove beyond end of code");
				}
				ilp = remove(ilp);
			}
			ilp = ilp_prev;
			for (PInst inst : pattern.getReplacement()) {
				Object[] args = new Object[inst.getArgs().size()];
				int a = 0;
				for (PExp arg : inst.getArgs()) {
					args[a++] = arg.eval();
				}
				Instruction i;
				try {
					i = (Instruction) inst.getOpcode().inst_class.getConstructors()[0].newInstance(args);
				} catch (Exception e) {
					throw new RuntimeException(
							"Error in instruction instantiation", e);
				}
				ilp = add(ilp, i);
			}
			checkLabels();
			mergeLabels();
			checkLabels();
			return true;
		}
		checkLabels();
		return false;
	}
	/*
	 * private void dump(InstructionList il) { while (il != null) { if (il.inst ==
	 * null) { System.err.println(" null"); } else { System.err.println("
	 * "+il.inst.toAsm()); } il = il.next; } }
	 */
}
